home *** CD-ROM | disk | FTP | other *** search
/ Delphi Magazine Collection 2001 / Delphi Magazine Collection 20001 (2001).iso / DISKS / Issue41 / Alfresco / Project1.dpr < prev   
Encoding:
Text File  |  1998-12-09  |  9.3 KB  |  352 lines
  1. program Project1;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6.   SysUtils,
  7.   AAGraphs in 'AAGraphs.pas';
  8.  
  9. procedure PreProcess(aSender : TObject; aNodeInx : integer;
  10.                      aExtraData : pointer);
  11. begin
  12.   writeln('PreProcessing node ', aNodeInx);
  13. end;
  14.  
  15. procedure PostProcess(aSender : TObject; aNodeInx : integer;
  16.                       aExtraData : pointer);
  17. begin
  18.   writeln('PostProcessing node ', aNodeInx);
  19. end;
  20.  
  21. procedure PrintNode(aSender : TObject; aNodeInx : integer;
  22.                     aExtraData : pointer);
  23. begin
  24.   writeln('Node ', aNodeInx);
  25. end;
  26.  
  27. const
  28.   EdgeExists = 1;
  29.  
  30. var
  31.   FMGraph : TaaFullMatrixGraph;
  32.   TMGraph : TaaTriMatrixGraph;
  33.   LLGraph : TaaLinkListGraph;
  34.   dfIter  : TaaDepthFirstIterator;
  35.   bfIter  : TaaBreadthFirstIterator;
  36.   i, j    : integer;
  37.   Edge    : longint;
  38.   ToInx   : integer;
  39.   HasCycle: boolean;
  40.  
  41. begin
  42.   try
  43.     FMGraph := TaaFullMatrixGraph.Create(10, false);
  44.     try
  45.       with FMGraph do begin
  46.         Edges[0, 6] := EdgeExists;
  47.         Edges[0, 9] := EdgeExists;
  48.         Edges[9, 8] := EdgeExists;
  49.         Edges[7, 8] := EdgeExists;
  50.         Edges[5, 6] := EdgeExists;
  51.         Edges[5, 4] := EdgeExists;
  52.         Edges[5, 3] := EdgeExists;
  53.         Edges[5, 8] := EdgeExists;
  54.         Edges[5, 7] := EdgeExists;
  55.         Edges[2, 1] := EdgeExists;
  56.         Edges[2, 3] := EdgeExists;
  57.         Edges[2, 4] := EdgeExists;
  58.         Edges[1, 3] := EdgeExists;
  59.         writeln('---full matrix graph');
  60.         writeln('   0 1 2 3 4 5 6 7 8 9');
  61.         for i := 0 to 9 do begin
  62.           write(i:2);
  63.           for j := 0 to 9 do begin
  64.             if Edges[i, j] <> EdgeNotPresent then
  65.               write(' 1')
  66.             else
  67.               write(' .');
  68.           end;
  69.           write('   ');
  70.           j := 0;
  71.           while GetNodeEdge(i, j, Edge, ToInx) do begin
  72.             write(ToInx:2);
  73.             inc(j);
  74.           end;
  75.           writeln;
  76.         end;
  77.       end;
  78.  
  79.       dfIter := TaaDepthFirstIterator.Create(FMGraph);
  80.       try
  81.         dfIter.OnPreProcess := PreProcess;
  82.         dfIter.OnPostProcess := PostProcess;
  83.         dfIter.Execute(0, HasCycle, nil);
  84.       finally
  85.         dfIter.Free;
  86.       end;
  87.  
  88.       bfIter := TaaBreadthFirstIterator.Create(FMGraph);
  89.       try
  90.         bfIter.OnPreProcess := PreProcess;
  91.         bfIter.OnPostProcess := PostProcess;
  92.         bfIter.Execute(0, nil);
  93.       finally
  94.         bfIter.Free;
  95.       end;
  96.     finally
  97.       FMGraph.Free;
  98.     end;
  99.     readln;
  100.     //
  101.     TMGraph := TaaTriMatrixGraph.Create(10);
  102.     try
  103.       with TMGraph do begin
  104.         Edges[0, 6] := EdgeExists;
  105.         Edges[0, 9] := EdgeExists;
  106.         Edges[9, 8] := EdgeExists;
  107.         Edges[7, 8] := EdgeExists;
  108.         Edges[5, 6] := EdgeExists;
  109.         Edges[5, 4] := EdgeExists;
  110.         Edges[5, 3] := EdgeExists;
  111.         Edges[5, 8] := EdgeExists;
  112.         Edges[5, 7] := EdgeExists;
  113.         Edges[2, 1] := EdgeExists;
  114.         Edges[2, 3] := EdgeExists;
  115.         Edges[2, 4] := EdgeExists;
  116.         Edges[1, 3] := EdgeExists;
  117.         writeln('---triangular matrix graph');
  118.         writeln('   0 1 2 3 4 5 6 7 8 9');
  119.         for i := 0 to 9 do begin
  120.           write(i:2);
  121.           for j := 0 to 9 do begin
  122.             if Edges[i, j] <> EdgeNotPresent then
  123.               write(' 1')
  124.             else
  125.               write(' .');
  126.           end;
  127.           write('   ');
  128.           j := 0;
  129.           while GetNodeEdge(i, j, Edge, ToInx) do begin
  130.             write(ToInx:2);
  131.             inc(j);
  132.           end;
  133.           writeln;
  134.         end;
  135.       end;
  136.  
  137.       dfIter := TaaDepthFirstIterator.Create(TMGraph);
  138.       try
  139.         dfIter.OnPreProcess := PreProcess;
  140.         dfIter.OnPostProcess := PostProcess;
  141.         dfIter.Execute(0, HasCycle, nil);
  142.       finally
  143.         dfIter.Free;
  144.       end;
  145.  
  146.       bfIter := TaaBreadthFirstIterator.Create(TMGraph);
  147.       try
  148.         bfIter.OnPreProcess := PreProcess;
  149.         bfIter.OnPostProcess := PostProcess;
  150.         bfIter.Execute(0, nil);
  151.       finally
  152.         bfIter.Free;
  153.       end;
  154.     finally
  155.       TMGraph.Free;
  156.     end;
  157.     readln;
  158.     //
  159.     LLGraph := TaaLinkListGraph.Create(10, false);
  160.     try
  161.       with LLGraph do begin
  162.         Edges[0, 6] := EdgeExists;
  163.         Edges[0, 9] := EdgeExists;
  164.         Edges[9, 8] := EdgeExists;
  165.         Edges[7, 8] := EdgeExists;
  166.         Edges[5, 6] := EdgeExists;
  167.         Edges[5, 4] := EdgeExists;
  168.         Edges[5, 3] := EdgeExists;
  169.         Edges[5, 8] := EdgeExists;
  170.         Edges[5, 7] := EdgeExists;
  171.         Edges[2, 1] := EdgeExists;
  172.         Edges[2, 3] := EdgeExists;
  173.         Edges[2, 4] := EdgeExists;
  174.         Edges[1, 3] := EdgeExists;
  175.         writeln('---linked list graph');
  176.         writeln('   0 1 2 3 4 5 6 7 8 9');
  177.         for i := 0 to 9 do begin
  178.           write(i:2);
  179.           for j := 0 to 9 do begin
  180.             if Edges[i, j] <> EdgeNotPresent then
  181.               write(' 1')
  182.             else
  183.               write(' .');
  184.           end;
  185.           write('   ');
  186.           j := 0;
  187.           while GetNodeEdge(i, j, Edge, ToInx) do begin
  188.             write(ToInx:2);
  189.             inc(j);
  190.           end;
  191.           writeln;
  192.         end;
  193.       end;
  194.  
  195.       dfIter := TaaDepthFirstIterator.Create(LLGraph);
  196.       try
  197.         dfIter.OnPreProcess := PreProcess;
  198.         dfIter.OnPostProcess := PostProcess;
  199.         dfIter.Execute(0, HasCycle, nil);
  200.       finally
  201.         dfIter.Free;
  202.       end;
  203.  
  204.       bfIter := TaaBreadthFirstIterator.Create(LLGraph);
  205.       try
  206.         bfIter.OnPreProcess := PreProcess;
  207.         bfIter.OnPostProcess := PostProcess;
  208.         bfIter.Execute(0, nil);
  209.         bfIter.OnPreProcess := nil;
  210.         bfIter.OnPostProcess := nil;
  211.         bfIter.OnPrintNode := PrintNode;
  212.         if not bfIter.ShortestPath(0, 7, nil) then
  213.           writeln('no path from 0 to 7');
  214.       finally
  215.         bfIter.Free;
  216.       end;
  217.     finally
  218.       LLGraph.Free;
  219.     end;
  220.     readln;
  221.     //
  222.     LLGraph := TaaLinkListGraph.Create(10, true);
  223.     try
  224.       with LLGraph do begin
  225.         Edges[0, 6] := EdgeExists;
  226.         Edges[0, 9] := EdgeExists;
  227.         Edges[9, 8] := EdgeExists;
  228.         Edges[7, 8] := EdgeExists;
  229.         Edges[5, 6] := EdgeExists;
  230.         Edges[5, 4] := EdgeExists;
  231.         Edges[5, 3] := EdgeExists;
  232.         Edges[5, 8] := EdgeExists;
  233.         Edges[5, 7] := EdgeExists;
  234.         Edges[2, 1] := EdgeExists;
  235.         Edges[2, 5] := EdgeExists;
  236.         Edges[2, 4] := EdgeExists;
  237.         Edges[1, 3] := EdgeExists;
  238.       //Edges[3, 2] := EdgeExists; {uncomment to cause cycle}
  239.         writeln('---linked list digraph');
  240.         writeln('   0 1 2 3 4 5 6 7 8 9');
  241.         for i := 0 to 9 do begin
  242.           write(i:2);
  243.           for j := 0 to 9 do begin
  244.             if Edges[i, j] <> EdgeNotPresent then
  245.               write(' 1')
  246.             else
  247.               write(' .');
  248.           end;
  249.           write('   ');
  250.           j := 0;
  251.           while GetNodeEdge(i, j, Edge, ToInx) do begin
  252.             write(ToInx:2);
  253.             inc(j);
  254.           end;
  255.           writeln;
  256.         end;
  257.       end;
  258.  
  259.       dfIter := TaaDepthFirstIterator.Create(LLGraph);
  260.       try
  261.         dfIter.OnProcessSortedNode := PrintNode;
  262.         dfIter.TopologicalSort(nil);
  263.       finally
  264.         dfIter.Free;
  265.       end;
  266.     finally
  267.       LLGraph.Free;
  268.     end;
  269.  
  270.     readln;
  271.     //
  272.     LLGraph := TaaLinkListGraph.Create(5, true);
  273.     try
  274.       with LLGraph do begin
  275.         Edges[0, 1] := 5;
  276.         Edges[0, 4] := 15;
  277.         Edges[1, 2] := 20;
  278.         Edges[1, 3] := 10;
  279.         Edges[3, 0] := 15;
  280.         Edges[3, 2] := 25;
  281.         Edges[3, 4] := 20;
  282.         writeln('---linked list weighted digraph');
  283.         writeln('    0  1  2  3  4');
  284.         for i := 0 to 4 do begin
  285.           write(i:2);
  286.           for j := 0 to 4 do begin
  287.             if Edges[i, j] <> EdgeNotPresent then
  288.               write(Edges[i, j]:3)
  289.             else
  290.               write('  .');
  291.           end;
  292.           write('   ');
  293.           j := 0;
  294.           while GetNodeEdge(i, j, Edge, ToInx) do begin
  295.             write(ToInx:2);
  296.             inc(j);
  297.           end;
  298.           writeln;
  299.         end;
  300.       end;
  301.  
  302.       MinSpanningTree(LLGraph, PrintNode, nil);
  303.  
  304.     finally
  305.       LLGraph.Free;
  306.     end;
  307.     readln;
  308.     //
  309.     LLGraph := TaaLinkListGraph.Create(5, true);
  310.     try
  311.       with LLGraph do begin
  312.         Edges[0, 1] := 5;
  313.         Edges[0, 4] := 50;
  314.         Edges[1, 2] := 40;
  315.         Edges[1, 3] := 10;
  316.         Edges[2, 4] := 5;
  317.         Edges[3, 2] := 10;
  318.         Edges[3, 4] := 20;
  319.         Edges[4, 1] := 15;
  320.         writeln('---linked list weighted digraph');
  321.         writeln('    0  1  2  3  4');
  322.         for i := 0 to 4 do begin
  323.           write(i:2);
  324.           for j := 0 to 4 do begin
  325.             if Edges[i, j] <> EdgeNotPresent then
  326.               write(Edges[i, j]:3)
  327.             else
  328.               write('  .');
  329.           end;
  330.           write('   ');
  331.           j := 0;
  332.           while GetNodeEdge(i, j, Edge, ToInx) do begin
  333.             write(ToInx:2);
  334.             inc(j);
  335.           end;
  336.           writeln;
  337.         end;
  338.       end;
  339.  
  340.       SmallestCostPath(LLGraph, 0, 4, PrintNode, nil);
  341.  
  342.     finally
  343.       LLGraph.Free;
  344.     end;
  345.  
  346.   except
  347.     on E:Exception do
  348.       writeln(E.Message);
  349.   end;
  350.   readln;
  351. end.
  352.